import Data.List
mulMod :: Integral a => a -> a -> a -> a
mulMod a b c= (b * c) `rem` a
squareMod :: Integral a => a -> a -> a
squareMod a b = (b * b) `rem` a
pow' :: (Num a, Integral b) => (a -> a -> a) -> (a -> a) -> a -> b -> a
pow' _ _ _ 0 = 1
pow' mul sq x' n' = f x' n' 1
    where
    f x n y
        | n == 1 = x `mul` y
        | r == 0 = f x2 q y
        | otherwise = f x2 q (x `mul` y)
        where
            (q,r) = quotRem n 2
            x2 = sq x
powMod :: Integral a => a -> a -> a -> a
powMod m = pow' (mulMod m) (squareMod m)
 
productMod =foldl (mulMod (10^5)) 1
hFacial 0=1
hFacial a
    |gcd a 5==1=mod (a*hFacial(a-1)) (5^5)
    |otherwise=hFacial(a-1)
fastFacial a= hFacial $mod a 6250
numPrime x p=takeWhile(>0) [div x (p^a)|a<-[1..]]
p160 x=mulMod t5 a b
    where
    t5=10^5
    lst=numPrime x 5
    a=powMod t5 1563 $mod c 2500
    b=productMod  c6 
    c=sum lst
    c6=map fastFacial $x:lst
problem_160 = p160 (10^12)